<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">Dense Scale Invariant Feature Transform (DSIFT) </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi </dd>
<dd>
Brian Fulkerson</dd></dl>
<p><a class="el" href="dsift_8h.html">dsift.h</a> implements a dense version of <a class="el" href="sift_8h.html">SIFT</a>. This is an object that can quickly compute descriptors for densely sampled keypoints with identical size and orientation. It can be reused for multiple images of the same size.</p>
<ul>
<li><a class="el" href="dsift.html#dsift-intro">Overview</a></li>
<li><a class="el" href="dsift.html#dsift-usage">Usage</a></li>
<li><a class="el" href="dsift.html#dsift-tech">Technical details</a><ul>
<li><a class="el" href="dsift.html#dsift-tech-descriptor-dense">Dense descriptors</a></li>
<li><a class="el" href="dsift.html#dsift-tech-sampling">Sampling</a></li>
</ul>
</li>
</ul>
<h2><a class="anchor" id="dsift-intro"></a>
Overview</h2>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="sift.html">The SIFT module</a>, <a class="el" href="dsift.html#dsift-tech">Technical details</a></dd></dl>
<p>This module implements a fast algorithm for the calculation of a large number of SIFT descriptors of densely sampled features of the same scale and orientation. See the <a class="el" href="sift.html">SIFT module</a> for an overview of SIFT.</p>
<p>The feature frames (keypoints) are indirectly specified by the sampling steps (<a class="el" href="dsift_8h.html#a42ae6bf77a9b737fd1e45ad5c43263dd" title="Set steps.">vl_dsift_set_steps</a>) and the sampling bounds (<a class="el" href="dsift_8h.html#a7d34c8e257c873f2ed580b046296d1ac" title="Set bounds.">vl_dsift_set_bounds</a>). The descriptor geometry (number and size of the spatial bins and number of orientation bins) can be customized (<a class="el" href="dsift_8h.html#a930f20c25eab08d9490830b0a358ff2b" title="Set SIFT descriptor geometry.">vl_dsift_set_geometry</a>, <a class="el" href="structVlDsiftDescriptorGeometry.html" title="Dense SIFT descriptor geometry.">VlDsiftDescriptorGeometry</a>).</p>
<div class="image">
<img src="dsift-geom.png" alt="dsift-geom.png"/>
<div class="caption">
Dense SIFT descriptor geometry</div></div>
<p> By default, SIFT uses a Gaussian windowing function that discounts contributions of gradients further away from the descriptor centers. This function can be changed to a flat window by invoking <a class="el" href="dsift_8h.html#a8dfe2d20dbe9885d0c139c5b81b5f4b0" title="Set flat window flag.">vl_dsift_set_flat_window</a>. In this case, gradients are accumulated using only bilinear interpolation, but instad of being reweighted by a Gassuain window, they are all weighted equally. However, after gradients have been accumulated into a spatial bin, the whole bin is reweighted by the average of the Gaussian window over the spatial support of that bin. This &ldquo;approximation&rdquo; substantially improves speed with little or no loss of performance in applications.</p>
<p>Keypoints are sampled in such a way that the centers of the spatial bins are at integer coordinates within the image boundaries. For instance, the top-left bin of the top-left descriptor is centered on the pixel (0,0). The bin immediately to the right at (<code>binSizeX</code>,0), where <code>binSizeX</code> is a paramtere in the <a class="el" href="structVlDsiftDescriptorGeometry.html" title="Dense SIFT descriptor geometry.">VlDsiftDescriptorGeometry</a> structure. <a class="el" href="dsift_8h.html#a7d34c8e257c873f2ed580b046296d1ac" title="Set bounds.">vl_dsift_set_bounds</a> can be used to further restrict sampling to the keypoints in an image.</p>
<h2><a class="anchor" id="dsift-usage"></a>
Usage</h2>
<p>DSIFT is implemented by a <a class="el" href="structVlDsiftFilter.html" title="Dense SIFT filter.">VlDsiftFilter</a> object that can be used to process a sequence of images of a given geometry. To use the <b>DSIFT filter</b>:</p>
<ul>
<li>Initialize a new DSIFT filter object by <a class="el" href="dsift_8h.html#a5f86d3d3a12bedab236a12e55a91edd1" title="Create a new DSIFT filter.">vl_dsift_new</a> (or the simplified <a class="el" href="dsift_8h.html#a100b0508f06275474caf3de958f09ea6" title="Create a new DSIFT filter (basic interface)">vl_dsift_new_basic</a>). Customize the descriptor parameters by <a class="el" href="dsift_8h.html#a42ae6bf77a9b737fd1e45ad5c43263dd" title="Set steps.">vl_dsift_set_steps</a>, <a class="el" href="dsift_8h.html#a930f20c25eab08d9490830b0a358ff2b" title="Set SIFT descriptor geometry.">vl_dsift_set_geometry</a>, etc.</li>
<li>Process an image by <a class="el" href="dsift_8h.html#a09d5525ad7e16e2b9f3f1b9d273c85f6" title="Compute keypoints and descriptors.">vl_dsift_process</a>.</li>
<li>Retrieve the number of keypoints (<a class="el" href="dsift_8h.html#a3b5fabb1496fc91a70669d4201f47a5b" title="Get number of keypoints.">vl_dsift_get_keypoint_num</a>), the keypoints (<a class="el" href="dsift_8h.html#a0cba85e88ae5232fe74368175a8ba510" title="Get keypoints.">vl_dsift_get_keypoints</a>), and their descriptors (<a class="el" href="dsift_8h.html#acd5425e9764383a5ef05bce00fd40e94" title="Get descriptors.">vl_dsift_get_descriptors</a>).</li>
<li>Optionally repeat for more images.</li>
<li>Delete the DSIFT filter by <a class="el" href="dsift_8h.html#aa123f1d9e79ab01882646f713dfb4f0c" title="Delete DSIFT filter.">vl_dsift_delete</a>.</li>
</ul>
<h2><a class="anchor" id="dsift-tech"></a>
Technical details</h2>
<p>This section extends the <a class="el" href="sift.html#sift-tech-descriptor">SIFT descriptor section</a> and specialzies it to the case of dense keypoints.</p>
<h3><a class="anchor" id="dsift-tech-descriptor-dense"></a>
Dense descriptors</h3>
<p>When computing descriptors for many keypoints differing only by their position (and with null rotation), further simplifications are possible. In this case, in fact,</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\begin{eqnarray*} \mathbf{x} &amp;=&amp; m \sigma \hat{\mathbf{x}} + T,\\ h(t,i,j) &amp;=&amp; m \sigma \int g_{\sigma_\mathrm{win}}(\mathbf{x} - T)\, w_\mathrm{ang}(\angle J(\mathbf{x}) - \theta_t)\, w\left(\frac{x - T_x}{m\sigma} - \hat{x}_i\right)\, w\left(\frac{y - T_y}{m\sigma} - \hat{y}_j\right)\, |J(\mathbf{x})|\, d\mathbf{x}. \end{eqnarray*}" src="form_44.png"/>
</p>
<p>Since many different values of <em>T</em> are sampled, this is conveniently expressed as a separable convolution. First, we translate by <img class="formulaInl" alt="$ \mathbf{x}_{ij} = m\sigma(\hat x_i,\ \hat y_i)^\top $" src="form_45.png"/> and we use the symmetry of the various binning and windowing functions to write</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\begin{eqnarray*} h(t,i,j) &amp;=&amp; m \sigma \int g_{\sigma_\mathrm{win}}(T' - \mathbf{x} - \mathbf{x}_{ij})\, w_\mathrm{ang}(\angle J(\mathbf{x}) - \theta_t)\, w\left(\frac{T'_x - x}{m\sigma}\right)\, w\left(\frac{T'_y - y}{m\sigma}\right)\, |J(\mathbf{x})|\, d\mathbf{x}, \\ T' &amp;=&amp; T + m\sigma \left[\begin{array}{cc} x_i \\ y_j \end{array}\right]. \end{eqnarray*}" src="form_46.png"/>
</p>
<p>Then we define kernels</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\begin{eqnarray*} k_i(x) &amp;=&amp; \frac{1}{\sqrt{2\pi} \sigma_{\mathrm{win}}} \exp\left( -\frac{1}{2} \frac{(x-x_i)^2}{\sigma_{\mathrm{win}}^2} \right) w\left(\frac{x}{m\sigma}\right), \\ k_j(y) &amp;=&amp; \frac{1}{\sqrt{2\pi} \sigma_{\mathrm{win}}} \exp\left( -\frac{1}{2} \frac{(y-y_j)^2}{\sigma_{\mathrm{win}}^2} \right) w\left(\frac{y}{m\sigma}\right), \end{eqnarray*}" src="form_47.png"/>
</p>
<p>and obtain</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\begin{eqnarray*} h(t,i,j) &amp;=&amp; (k_ik_j * \bar J_t)\left( T + m\sigma \left[\begin{array}{cc} x_i \\ y_j \end{array}\right] \right), \\ \bar J_t(\mathbf{x}) &amp;=&amp; w_\mathrm{ang}(\angle J(\mathbf{x}) - \theta_t)\,|J(\mathbf{x})|. \end{eqnarray*}" src="form_48.png"/>
</p>
<p>Furthermore, if we use a flat rather than Gaussian windowing function, the kernels do not depend on the bin, and we have</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\begin{eqnarray*} k(z) &amp;=&amp; \frac{1}{\sigma_{\mathrm{win}}} w\left(\frac{z}{m\sigma}\right), \\ h(t,i,j) &amp;=&amp; (k(x)k(y) * \bar J_t)\left( T + m\sigma \left[\begin{array}{cc} x_i \\ y_j \end{array}\right] \right), \end{eqnarray*}" src="form_49.png"/>
</p>
<p>(here <img class="formulaInl" alt="$ \sigma_\mathrm{win} $" src="form_50.png"/> is the side of the flat window).</p>
<dl class="note"><dt><b>Note:</b></dt><dd>In this case the binning functions <img class="formulaInl" alt="$ k(z) $" src="form_51.png"/> are triangular and the convolution can be computed in time independent on the filter (i.e. descriptor bin) support size by integral signals.</dd></dl>
<h3><a class="anchor" id="dsift-tech-sampling"></a>
Sampling</h3>
<p>To avoid resampling and dealing with special boundary conditions, we impose some mild restrictions on the geometry of the descriptors that can be computed. In particular, we impose that the bin centers <img class="formulaInl" alt="$ T + m\sigma (x_i,\ y_j) $" src="form_52.png"/> are always at integer coordinates within the image boundaries. This eliminates the need for costly interpolation. This condition amounts to (expressed in terms of the <em>x</em> coordinate, and equally applicable to <em>y</em>)</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \{0,\dots, W-1\} \ni T_x + m\sigma x_i = T_x + m\sigma i - \frac{N_x-1}{2} = \bar T_x + m\sigma i, \qquad i = 0,\dots,N_x-1. \]" src="form_53.png"/>
</p>
<p>Notice that for this condition to be satisfied, the <em>descriptor</em> center <img class="formulaInl" alt="$ T_x $" src="form_54.png"/> needs to be either fractional or integer depending on <img class="formulaInl" alt="$ N_x $" src="form_55.png"/> being even or odd. To eliminate this complication, it is simpler to use as a reference not the descriptor center <em>T</em>, but the coordinates of the upper-left bin <img class="formulaInl" alt="$ \bar T $" src="form_56.png"/>. Thus we sample the latter on a regular (integer) grid</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \left[\begin{array}{cc} 0 \\ 0 \end{array}\right] \leq \bar T = \left[\begin{array}{cc} \bar T_x^{\min} + p \Delta_x \\ \bar T_y^{\min} + q \Delta_y \\ \end{array}\right] \leq \left[\begin{array}{cc} W - 1 - m\sigma N_x \\ H - 1 - m\sigma N_y \end{array}\right], \quad \bar T = \left[\begin{array}{cc} T_x - \frac{N_x - 1}{2} \\ T_y - \frac{N_y - 1}{2} \\ \end{array}\right] \]" src="form_57.png"/>
</p>
<p>and we impose that the bin size <img class="formulaInl" alt="$ m \sigma $" src="form_58.png"/> is integer as well. </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
